{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "# Hash map\n",
        "A hash map is a data structure that maps keys to values with amortized O(1) insertion, find, and deletion time. The map is unordered.\n",
        "\n",
        "Open3D allows parallel hashing on CPU and GPU with keys and values organized as Tensors, where we take a batch of keys and/or values as input.\n",
        "\n",
        "- Keys: The Open3D hash map supports multi-dimensional keys. Due to precision issue, floating-point is not recommended to be regarded as keys. By default we support up to 6D coordinates in integer. For higher dimensions, you may modify the macros and compile from source in [this file](https://github.com/isl-org/Open3D/blob/main/cpp/open3d/core/hashmap/Dispatch.h) within this snippet:\n",
        "\n",
        "```cpp\n",
        "#define DIM_SWITCHER(DTYPE, DIM, ...)                                    \\\n",
        "    if (DIM == 1) {                                                      \\\n",
        "        INSTANTIATE_TYPES(DTYPE, 1)                                      \\\n",
        "        return __VA_ARGS__();                                            \\\n",
        "    } else if (DIM == 2) {                                               \\\n",
        "        INSTANTIATE_TYPES(DTYPE, 2)                                      \\\n",
        "        return __VA_ARGS__();                                            \\\n",
        "    } else if (DIM == 3) {                                               \\\n",
        "        INSTANTIATE_TYPES(DTYPE, 3)                                      \\\n",
        "        return __VA_ARGS__();                                            \\\n",
        "    } else if (DIM == 4) {                                               \\\n",
        "        INSTANTIATE_TYPES(DTYPE, 4)                                      \\\n",
        "        return __VA_ARGS__();                                            \\\n",
        "    } else if (DIM == 5) {                                               \\\n",
        "        INSTANTIATE_TYPES(DTYPE, 5)                                      \\\n",
        "        return __VA_ARGS__();                                            \\\n",
        "    } else if (DIM == 6) {                                               \\\n",
        "        INSTANTIATE_TYPES(DTYPE, 6)                                      \\\n",
        "        return __VA_ARGS__();                                            \\\n",
        "    } else {                                                             \\\n",
        "        utility::LogError(                                               \\\n",
        "                \"Unsupported dim {}, please modify {} and compile from \" \\\n",
        "                \"source\",                                                \\\n",
        "                DIM, __FILE__);                                          \\\n",
        "    }\n",
        "```\n",
        "\n",
        "- Values: The Open3D hash map supports values in arbitrary dimensions and data types.\n",
        "- Devices: Both CPU and CUDA are supported. The CPU hashmap is based on [TBB](https://github.com/oneapi-src/oneTBB), while the CUDA hash map is based upon [stdgpu](https://github.com/stotko/stdgpu)."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {},
      "outputs": [],
      "source": [
        "import open3d.core as o3c\n",
        "import numpy as np\n",
        "\n",
        "capacity = 10\n",
        "device = o3c.Device('cpu:0')"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## A simple example\n",
        "We first create a simple hash map from integers to integers.\n",
        "\n",
        "We specify an initial estimated capacity. This capacity will be automatically adjusted when insertion occurs. Then we specify the element shape of keys and values, corresponding to the shape of each individual element."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 2,
      "metadata": {},
      "outputs": [],
      "source": [
        "hashmap = o3c.HashMap(capacity,\n",
        "                      key_dtype=o3c.int64,\n",
        "                      key_element_shape=(1,),\n",
        "                      value_dtype=o3c.int64,\n",
        "                      value_element_shape=(1,),\n",
        "                      device=device)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Insertion\n",
        "Next we show how to insert a batch of (key, value) pairs. You'll need to prepare two tensors:\n",
        "\n",
        "The `keys` tensor contains all keys. \n",
        "\n",
        "- The `keys` tensor must be on the same device as the hash map. \n",
        "- The shape of the `keys` tensor is `key_elment_shape` with `N` prefixed to the front. \n",
        "\n",
        "For example \n",
        " \n",
        "1. if `key_element_shape == ()`, `keys.shape == (N,)`; \n",
        "2. if `key_element_shape == (3,)`, `keys.shape == (N, 3).`; \n",
        "3. if `key_element_shape == (8, 8, 8)`, `keys.shape == (N, 8, 8, 8).`\n",
        "    \n",
        "The `vals` tensor contains all values. \n",
        " \n",
        "- The `vals` tensor must be on the same device as the hash map. \n",
        "- The shape of the `vals` tensor is `val_elment_shape` with `N` prefixed to the front. \n",
        "\n",
        "For example \n",
        "\n",
        "1. if `val_elment_shape == ()`, `vals.shape == (N,)`; \n",
        "2. if `val_elment_shape == (3,)`, `vals.shape == (N, 3).`;\n",
        "3. if `val_elment_shape == (8, 8, 8)`, `vals.shape == (N, 8, 8, 8).`"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 3,
      "metadata": {},
      "outputs": [],
      "source": [
        "# Prepare a batch of 7 key/values, each a int64 element\n",
        "keys = o3c.Tensor([[100], [200], [400], [800], [300], [200], [100]],\n",
        "                  dtype=o3c.int64,\n",
        "                  device=device)\n",
        "vals = o3c.Tensor([[1], [2], [4], [8], [3], [2], [1]],\n",
        "                  dtype=o3c.int64,\n",
        "                  device=device)\n",
        "buf_indices, masks = hashmap.insert(keys, vals)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Here, `masks` indicates whether a (key, value) pair is successfully inserted. \n",
        "A mask of value `True` means the insertion is successful and `False` if the insertion is skipped.\n",
        "\n",
        "Unsuccessful insertion only happens when there are duplicated keys. \n",
        "\n",
        "If there are duplicated keys, it is guaranteed that only **one** of the duplicated keys and its corresponding value will be inserted. That is, for a set of duplicated keys, one and only one will get a `True` mask. \n",
        "\n",
        "Since the insertion runs in parallel, there is no guarantee **which one** of the duplicated keys will be inserted. That is, for a set of duplicated keys, we don't know which key gets the `True` mask.\n",
        "\n",
        "Using advanced indexing, we can obtain which keys are inserted:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 4,
      "metadata": {
        "scrolled": true
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "masks: \n",
            " [True True True True True False False]\n",
            "Tensor[shape={7}, stride={1}, Bool, CPU:0, 0x5571293a85a0]\n",
            "inserted keys: \n",
            " [[100],\n",
            " [200],\n",
            " [400],\n",
            " [800],\n",
            " [300]]\n",
            "Tensor[shape={5, 1}, stride={1, 1}, Int64, CPU:0, 0x557128c4f760]\n"
          ]
        }
      ],
      "source": [
        "print('masks: \\n', masks)\n",
        "print('inserted keys: \\n', keys[masks])"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Next, let's look at the usage of `buf_indices`. In our hash map, keys and values are stored in contiguous buffer tensors that could be conveniently accessed by indices. Instead of returning iterators that are less friendly to vectorized programming, we return such buffer indices. \n",
        "\n",
        "<div class=\"alert alert-info\">\n",
        "These indices are not necessarily the same as input indices due to concurrency. Also, the indices are by default stored in int32 due to the underlying implementations. A conversion to int64 is required for advanced indexing.\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 5,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "buffer indices: \n",
            " [0 1 3 4 2]\n",
            "Tensor[shape={5}, stride={1}, Int64, CPU:0, 0x5571293ae6d0]\n",
            "inserted keys: \n",
            " [[100],\n",
            " [200],\n",
            " [400],\n",
            " [800],\n",
            " [300]]\n",
            "Tensor[shape={5, 1}, stride={1, 1}, Int64, CPU:0, 0x5571284a73b0]\n",
            "inserted values: \n",
            " [[1],\n",
            " [2],\n",
            " [4],\n",
            " [8],\n",
            " [3]]\n",
            "Tensor[shape={5, 1}, stride={1, 1}, Int64, CPU:0, 0x5571284a6f50]\n"
          ]
        }
      ],
      "source": [
        "buf_keys = hashmap.key_tensor()\n",
        "buf_vals = hashmap.value_tensor()\n",
        "buf_indices = buf_indices[masks].to(o3c.int64)\n",
        "print('buffer indices: \\n', buf_indices)\n",
        "\n",
        "inserted_keys = buf_keys[buf_indices]\n",
        "inserted_vals = buf_vals[buf_indices]\n",
        "print('inserted keys: \\n', inserted_keys)\n",
        "print('inserted values: \\n', inserted_vals)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Query\n",
        "The query operation follows the similar convention. Note as the operation is read-only, duplicate keys are allowed and will be returned properly."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 6,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "found valid keys: \n",
            " [[100],\n",
            " [300],\n",
            " [200],\n",
            " [100]]\n",
            "Tensor[shape={4, 1}, stride={1, 1}, Int64, CPU:0, 0x5571293a3ae0]\n",
            "found valid values: \n",
            " [[1],\n",
            " [3],\n",
            " [2],\n",
            " [1]]\n",
            "Tensor[shape={4, 1}, stride={1, 1}, Int64, CPU:0, 0x5571293ae6d0]\n"
          ]
        }
      ],
      "source": [
        "query_keys = o3c.Tensor([[1000], [100], [300], [200], [100], [0]],\n",
        "                        dtype=o3c.int64,\n",
        "                        device=device)\n",
        "buf_indices, masks = hashmap.find(query_keys)\n",
        "valid_keys = query_keys[masks]\n",
        "buf_indices = buf_indices[masks].to(o3c.int64)\n",
        "valid_vals = hashmap.value_tensor()[buf_indices]\n",
        "print('found valid keys: \\n', valid_keys)\n",
        "print('found valid values: \\n', valid_vals)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Active entries in the hash map\n",
        "Sometimes we are interested in all the active entries. This can be achieved by:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 7,
      "metadata": {},
      "outputs": [],
      "source": [
        "def print_active_entries(hashmap):\n",
        "    active_buf_indices = hashmap.active_buf_indices().to(o3c.int64)\n",
        "\n",
        "    active_keys = hashmap.key_tensor()[active_buf_indices]\n",
        "    print('all active keys:\\n', active_keys)\n",
        "\n",
        "    active_vals = hashmap.value_tensor()[active_buf_indices]\n",
        "    print('all active values:\\n', active_vals)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Again, due to concurrency, the order is not guaranteed, but the key-value correspondence will be of course preserved."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Erase\n",
        "We can similarly erase keys. The behavior is similar to insert:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 8,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "erase masks:\n",
            " [True False False]\n",
            "Tensor[shape={3}, stride={1}, Bool, CPU:0, 0x5571292dd430]\n",
            "erased keys:\n",
            " [[100]]\n",
            "Tensor[shape={1, 1}, stride={1, 1}, Int64, CPU:0, 0x5571284a6a10]\n"
          ]
        }
      ],
      "source": [
        "erase_keys = o3c.Tensor([[100], [1000], [100]], dtype=o3c.int64, device=device)\n",
        "masks = hashmap.erase(erase_keys)\n",
        "print('erase masks:\\n', masks)\n",
        "print('erased keys:\\n', erase_keys[masks])"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Now we can see that active entries have been changed:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 9,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "all active keys:\n",
            " [[300],\n",
            " [200],\n",
            " [400],\n",
            " [800]]\n",
            "Tensor[shape={4, 1}, stride={1, 1}, Int64, CPU:0, 0x5571293a9ad0]\n",
            "all active values:\n",
            " [[3],\n",
            " [2],\n",
            " [4],\n",
            " [8]]\n",
            "Tensor[shape={4, 1}, stride={1, 1}, Int64, CPU:0, 0x5571293b1d10]\n"
          ]
        }
      ],
      "source": [
        "print_active_entries(hashmap)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Activate\n",
        "In some cases, we know a key is occupied, but do not know the associated value - we prefer to compute and modify it in-place afterwards. This can be achieved by a chain of operations:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 10,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "all active keys:\n",
            " [[300],\n",
            " [1000],\n",
            " [200],\n",
            " [400],\n",
            " [0],\n",
            " [800]]\n",
            "Tensor[shape={6, 1}, stride={1, 1}, Int64, CPU:0, 0x5571284a6b00]\n",
            "all active values:\n",
            " [[3],\n",
            " [10],\n",
            " [2],\n",
            " [4],\n",
            " [0],\n",
            " [8]]\n",
            "Tensor[shape={6, 1}, stride={1, 1}, Int64, CPU:0, 0x5571284a6a60]\n"
          ]
        }
      ],
      "source": [
        "activate_keys = o3c.Tensor([[1000], [0]], dtype=o3c.int64, device=device)\n",
        "buf_indices, masks = hashmap.activate(activate_keys)\n",
        "\n",
        "buf_vals = hashmap.value_tensor()\n",
        "# Note the assigned tensor has to be strictly in the shape of (N, 1) due to broadcasting\n",
        "buf_vals[buf_indices[masks].to(o3c.int64)] \\\n",
        "    = o3c.Tensor([[10], [0]],\n",
        "                 dtype=o3c.int64,\n",
        "                 device=device)\n",
        "\n",
        "print_active_entries(hashmap)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Rehashing and reserve\n",
        "Rehashing will be automatically triggered when the initial capacity is exceeded after multiple insertions, where the capacity of the hash map is doubled. Rehashing will change the location (i.e. buffer indices) of the inserted key-value pairs, so an update of the buffer indices in the downstream applications is required."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 11,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "size: 6\n",
            "capacity: 10\n",
            "size: 9\n",
            "capacity: 10\n",
            "all active keys:\n",
            " [[300],\n",
            " [1500],\n",
            " [700],\n",
            " [1000],\n",
            " [200],\n",
            " [400],\n",
            " [1200],\n",
            " [0],\n",
            " [800]]\n",
            "Tensor[shape={9, 1}, stride={1, 1}, Int64, CPU:0, 0x5571293b4d80]\n",
            "all active values:\n",
            " [[3],\n",
            " [-1],\n",
            " [7],\n",
            " [10],\n",
            " [2],\n",
            " [4],\n",
            " [12],\n",
            " [0],\n",
            " [8]]\n",
            "Tensor[shape={9, 1}, stride={1, 1}, Int64, CPU:0, 0x5571293b64d0]\n",
            "size: 12\n",
            "capacity: 20\n",
            "all active keys:\n",
            " [[1700],\n",
            " [300],\n",
            " [1500],\n",
            " [700],\n",
            " [1000],\n",
            " [200],\n",
            " [1800],\n",
            " [400],\n",
            " [1200],\n",
            " [1600],\n",
            " [0],\n",
            " [800]]\n",
            "Tensor[shape={12, 1}, stride={1, 1}, Int64, CPU:0, 0x5571293b6410]\n",
            "all active values:\n",
            " [[17],\n",
            " [3],\n",
            " [-1],\n",
            " [7],\n",
            " [10],\n",
            " [2],\n",
            " [18],\n",
            " [4],\n",
            " [12],\n",
            " [16],\n",
            " [0],\n",
            " [8]]\n",
            "Tensor[shape={12, 1}, stride={1, 1}, Int64, CPU:0, 0x5571293b8250]\n"
          ]
        }
      ],
      "source": [
        "print('size:', hashmap.size())\n",
        "print('capacity:', hashmap.capacity())\n",
        "\n",
        "keys = o3c.Tensor([[700], [1200], [1500]], dtype=o3c.int64, device=device)\n",
        "vals = o3c.Tensor([[7], [12], [-1]], dtype=o3c.int64, device=device)\n",
        "buf_indices, masks = hashmap.insert(keys, vals)\n",
        "print('size:', hashmap.size())\n",
        "print('capacity:', hashmap.capacity())\n",
        "print_active_entries(hashmap)\n",
        "\n",
        "keys = o3c.Tensor([[1600], [1700], [1800]], dtype=o3c.int64, device=device)\n",
        "vals = o3c.Tensor([[16], [17], [18]], dtype=o3c.int64, device=device)\n",
        "buf_indices, masks = hashmap.insert(keys, vals)\n",
        "print('size:', hashmap.size())\n",
        "print('capacity:', hashmap.capacity())\n",
        "print_active_entries(hashmap)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Rehashing is slow, as it increases the hash map capacity, collects all the active entries, and insert them back to the hash map. If we know the capacity beforehand, we can pre-allocate a chunk of memory and avoid rehashing:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 12,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "size: 12\n",
            "capacity: 100\n"
          ]
        }
      ],
      "source": [
        "hashmap.reserve(100)\n",
        "print('size:', hashmap.size())\n",
        "print('capacity:', hashmap.capacity())"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Multi-valued hash map"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "In real-world applications, we want to map coordinates to complex data structures, e.g. a voxel position to its color and weight. This can be achieved by a multi-valued hash map. \n",
        "\n",
        "<div class=\"alert alert-info\">\n",
        "This is not a multimap and does not allow duplicate keys. A multi-valued hash map can be constructed by\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 13,
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "([1 0 2]\n",
              " Tensor[shape={3}, stride={1}, Int32, CPU:0, 0x5571293b83f0],\n",
              " [True True True]\n",
              " Tensor[shape={3}, stride={1}, Bool, CPU:0, 0x5571293bab60])"
            ]
          },
          "execution_count": 13,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "mhashmap = o3c.HashMap(capacity,\n",
        "                       key_dtype=o3c.int32,\n",
        "                       key_element_shape=(3,),\n",
        "                       value_dtypes=(o3c.uint8, o3c.float32),\n",
        "                       value_element_shapes=((3,), (1,)),\n",
        "                       device=device)\n",
        "voxel_coords = o3c.Tensor([[0, 1, 0], [-1, 2, 3], [3, 4, 1]],\n",
        "                          dtype=o3c.int32,\n",
        "                          device=device)\n",
        "voxel_colors = o3c.Tensor([[0, 255, 0], [255, 255, 0], [255, 0, 0]],\n",
        "                          dtype=o3c.uint8,\n",
        "                          device=device)\n",
        "voxel_weights = o3c.Tensor([[0.9], [0.1], [0.3]],\n",
        "                           dtype=o3c.float32,\n",
        "                           device=device)\n",
        "mhashmap.insert(voxel_coords, (voxel_colors, voxel_weights))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "We can then query and access by indices with a slightly different routine:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 14,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "found coordinates:\n",
            " [[0 1 0]]\n",
            "Tensor[shape={1, 3}, stride={3, 1}, Int32, CPU:0, 0x5571293c47c0]\n",
            "found colors:\n",
            " [[0 255 0]]\n",
            "Tensor[shape={1, 3}, stride={3, 1}, UInt8, CPU:0, 0x5571293c47a0]\n",
            "found weights:\n",
            " [[0.9]]\n",
            "Tensor[shape={1, 1}, stride={1, 1}, Float32, CPU:0, 0x5571284a6540]\n"
          ]
        }
      ],
      "source": [
        "query_coords = o3c.Tensor([[0, 1, 0]], dtype=o3c.int32, device=device)\n",
        "buf_indices, masks = mhashmap.find(query_coords)\n",
        "\n",
        "valid_keys = query_coords[masks]\n",
        "buf_indices = buf_indices[masks].to(o3c.int64)\n",
        "valid_colors = mhashmap.value_tensor(0)[buf_indices]\n",
        "valid_weights = mhashmap.value_tensor(1)[buf_indices]\n",
        "print('found coordinates:\\n', valid_keys)\n",
        "print('found colors:\\n', valid_colors)\n",
        "print('found weights:\\n', valid_weights)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 15,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "all active keys:\n",
            " [[0 1 0],\n",
            " [3 4 1],\n",
            " [-1 2 3]]\n",
            "Tensor[shape={3, 3}, stride={3, 1}, Int32, CPU:0, 0x5571293b1d40]\n",
            "active value 0\n",
            ": [[0 255 0],\n",
            " [255 0 0],\n",
            " [255 255 0]]\n",
            "Tensor[shape={3, 3}, stride={3, 1}, UInt8, CPU:0, 0x5571293c5610]\n",
            "active value 1\n",
            ": [[0.9],\n",
            " [0.3],\n",
            " [0.1]]\n",
            "Tensor[shape={3, 1}, stride={1, 1}, Float32, CPU:0, 0x5571293c56d0]\n"
          ]
        }
      ],
      "source": [
        "def print_active_multivalue_entries(mhashmap):\n",
        "    active_buf_indices = mhashmap.active_buf_indices().to(o3c.int64)\n",
        "\n",
        "    active_keys = mhashmap.key_tensor()[active_buf_indices]\n",
        "    print('all active keys:\\n', active_keys)\n",
        "\n",
        "    n_buffers = len(mhashmap.value_tensors())\n",
        "    for i in range(n_buffers):\n",
        "        active_val_i = mhashmap.value_tensor(i)[active_buf_indices]\n",
        "        print('active value {}\\n:'.format(i), active_val_i)\n",
        "\n",
        "\n",
        "print_active_multivalue_entries(mhashmap)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Hash set\n",
        "Hash set is a simplified hash map where we do not care about the values. It preserves most of the operations in a hash map, and could be useful for removing duplicates."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 16,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "active keys:\n",
            " [[5],\n",
            " [9],\n",
            " [1],\n",
            " [3],\n",
            " [11],\n",
            " [7]]\n",
            "Tensor[shape={6, 1}, stride={1, 1}, Int64, CPU:0, 0x5571284a6b00]\n"
          ]
        }
      ],
      "source": [
        "hashset = o3c.HashSet(capacity,\n",
        "                      key_dtype=o3c.int64,\n",
        "                      key_element_shape=(1,),\n",
        "                      device=device)\n",
        "keys = o3c.Tensor([1, 3, 5, 7, 5, 3, 1], dtype=o3c.int64,\n",
        "                  device=device).reshape((-1, 1))\n",
        "hashset.insert(keys)\n",
        "\n",
        "keys = o3c.Tensor([5, 7, 9, 11], dtype=o3c.int64, device=device).reshape(\n",
        "    (-1, 1))\n",
        "hashset.insert(keys)\n",
        "\n",
        "\n",
        "def print_active_keys(hashset):\n",
        "    active_buf_indices = hashset.active_buf_indices().to(o3c.int64)\n",
        "    active_keys = hashset.key_tensor()[active_buf_indices]\n",
        "    print('active keys:\\n', active_keys)\n",
        "\n",
        "\n",
        "print_active_keys(hashset)"
      ]
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.7.9"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 4
}
